package leetcode_top;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import org.junit.*;
public class Ex127 {
    class Solution1 {
        
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            this.list = wordList;
            dfs(beginWord, endWord, new LinkedHashSet<>(){{add(beginWord);}});
            System.out.println(res);
            return res == null ? 0 : res.size();
        }
        List<String> list;
        List<String> res = null;
        public void dfs(String cur, String tar, Set<String> tmp) {
            if (cur.equals(tar)) {
                if (res == null || res.size() > tmp.size()) {
                    res = new ArrayList<>(tmp);
                }
                return;
            }
            list.forEach(s -> {
                if (!tmp.contains(s) && isNear(s, cur)) {
                    tmp.add(s);
                    dfs(s, tar, tmp);
                    tmp.remove(s);
                }
            });
        }

        public boolean isNear(String s, String t) {
            int count = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != t.charAt(i)) count++;
                if(count > 1) return false;
            }
            return count == 1;
        }
    }

    class Solution {
        
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            Queue<String> queue = new LinkedList<>();
            queue.offer(beginWord);
            Set<String> visited = new HashSet<>();
            visited.add(beginWord);
            Set<String> dict = new HashSet<>(wordList);
            char[] cs;
            int step = 1, n, len = beginWord.length();
            while (!queue.isEmpty()) {
                n = queue.size();
                for (int i = 0; i < n; i++) {
                    cs = queue.poll().toCharArray();
                    for (int j = 0; j < len; j++) {
                        for (int k = 0; k < 26; k++) {
                            if (k + 'a' == cs[j]) continue;
                            char c = cs[j];
                            cs[j] = (char)(k + 'a');
                            String s = new String(cs);
                            if (dict.contains(s)) {
                                if (s.equals(endWord)) {
                                    return step + 1;
                                }
                                if (!visited.contains(s)) {
                                    visited.add(s);
                                    queue.offer(s);
                                }
                            }
                            cs[j] = c; //注意必须要改回去
                        }
                    }
                }
                step++;
            }
            return 0;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        String[] strs = {"hot","dot","dog","lot","log","cog"}; 
        // strs = new String[]{"hot","dot","dog","lot","log"};   
        System.out.println(s.ladderLength("hit", "cog", Stream.of(strs).collect(Collectors.toList())));    
    }



public class Solution2 {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 第 1 步：先将 wordList 放到哈希表里，便于判断某个单词是否在 wordList 里
        Set<String> wordSet = new HashSet<>(wordList);
        if (wordSet.size() == 0 || !wordSet.contains(endWord)) {
            return 0;
        }
        wordSet.remove(beginWord);
        
        // 第 2 步：图的广度优先遍历，必须使用队列和表示是否访问过的 visited 哈希表
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        
        // 第 3 步：开始广度优先遍历，包含起点，因此初始化的时候步数为 1
        int step = 1;
        while (!queue.isEmpty()) {
            int currentSize = queue.size();
            for (int i = 0; i < currentSize; i++) {
                // 依次遍历当前队列中的单词
                String currentWord = queue.poll();
                // 如果 currentWord 能够修改 1 个字符与 endWord 相同，则返回 step + 1
                if (changeWordEveryOneLetter(currentWord, endWord, queue, visited, wordSet)) {
                    return step + 1;
                }
            }
            step++;
        }
        return 0;
    }

    /**
     * 尝试对 currentWord 修改每一个字符，看看是不是能与 endWord 匹配
     *
     * @param currentWord
     * @param endWord
     * @param queue
     * @param visited
     * @param wordSet
     * @return
     */
    private boolean changeWordEveryOneLetter(String currentWord, String endWord,
                                             Queue<String> queue, Set<String> visited, Set<String> wordSet) {
        char[] charArray = currentWord.toCharArray();
        for (int i = 0; i < endWord.length(); i++) {
            // 先保存，然后恢复
            char originChar = charArray[i];
            for (char k = 'a'; k <= 'z'; k++) {
                if (k == originChar) {
                    continue;
                }
                charArray[i] = k;
                String nextWord = String.valueOf(charArray);
                if (wordSet.contains(nextWord)) {
                    if (nextWord.equals(endWord)) {
                        return true;
                    }
                    if (!visited.contains(nextWord)) {
                        queue.add(nextWord);
                        // 注意：添加到队列以后，必须马上标记为已经访问
                        visited.add(nextWord);
                    }
                }
            }
            // 恢复
            charArray[i] = originChar;
        }
        return false;
    }
}

}
